#include <bits/stdc++.h>

using namespace std;

// 返回两个无环链表相交的第一个节点
// 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/

// 不需要提交这个类
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 提交这个类即可
class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *h1, ListNode *h2) 
    {
        if(h1 == nullptr || h2 == nullptr) return nullptr;
        ListNode *a = h1, *b = h2;
        int diff = 0;
        while(a->next != nullptr)
        {
            a = a->next;
            ++diff;
        }
        while(b->next != nullptr)
        {
            b = b->next;
            --diff;
        }
        // 如果链表的最后一个节点不相同，那么两个链表不相交
        if(a != b) return nullptr;
        // a 默认是长链表
        if(diff >= 0)
            a = h1, b = h2;
        else
            a = h2, b = h1;
        diff = abs(diff);
        // 长链表先走 diff 步，然后长短链表一起走
        while(diff--)
        {
            a = a->next;
        }
        while(a != b)
        {
            a = a->next;
            b = b->next;
        }
        return a;
    }
};